package algorithm.sort.child;

import algorithm.sort.basic.Sort;

import java.util.*;

/**
 * 项目名称: god
 * 包 名 称: algorithm.sort.child
 * 类 名 称: BucketSort
 * 类 描 述: TODO
 * 创建时间: 2020/6/28 10:56 上午
 * 创 建 人: Justice
 * Bucket sort<br>
 * 桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。<br>
 * <br>执行流程如下<br>
 * 1 设置一个定量的数组当作空桶子。<bR>
 * 2 寻访串行，并且把项目一个一个放到对应的桶子去。<bR>
 * 3 对每个不是空的桶子进行排序。<bR>
 * 4 从不是空的桶子里把项目再放回原来的串行中。<bR>
 */
public class BucketSort extends Sort<Integer> {

    @Override
    protected void sort() {
        int length = array.length;
        LinkedNode[] bucket = new LinkedNode[length];  // 桶的个数等于length
        int max = array[0];  // 求max
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        // 入桶
        // 扫描每个元素
        for (int value : array) {
            int hash = hash(value, max, length);  // 桶的下标
            if (bucket[hash] == null) {
                bucket[hash] = new LinkedNode(value);  // 初始化链表
            } else {
                insertInto(value, bucket[hash], bucket, hash);  // 插入链表
            }
        }
        int k = 0; // 记录数组下标
        // 出桶，回填arr
        for (LinkedNode node : bucket) {
            if (node != null) {
                while (node != null) {
                    array[k++] = node.value;
                    node = node.next;
                }
            }
        }
    }

    // 根据桶的个数来确定hash函数，这份代码适合桶的个数等于数组长度
    static int hash(int element, int max, int length) {
        return (element * length) / (max + 1);
    }

    private static void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {
        LinkedNode newNode = new LinkedNode(value);
        // 小于头节点，放在头上
        if (value <= head.value) {
            newNode.next = head;
            // 替换头节点
            bucket[hash] = newNode;
            return;
        }
        // 往后找第一个比当前值大的节点，放在这个节点的前面
        LinkedNode p = head;
        LinkedNode pre = p;
        while (p != null && value > p.value) {
            pre = p;
            p = p.next;
        }
        if (p == null) {  // 跑到末尾了
            pre.next = newNode;
        } else {             // 插入pre和p之间
            pre.next = newNode;
            newNode.next = p;
        }
    }

}

/**
 * 简单单向链表的节点
 */
class LinkedNode {
    public int value;
    public LinkedNode next;

    public LinkedNode(int value) {
        this.value = value;
    }
}